import java.util.*;

public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;//引用左子树；
        public TreeNode right;//引用右子树；

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        return A;
    }
    //前序遍历；
    public void preOrder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //中序遍历；
    public void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    //后序遍历；
    public void postOrder(TreeNode root){
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    //前序遍历的结果值保存；
    //方法一；
    List<Character> list1=new ArrayList<>();
    public List<Character> preorderTraversal1(TreeNode root){
        if(root==null){
            return list1;
        }
        list1.add(root.val);
        preorderTraversal1(root.left);
        preorderTraversal1((root.right));
        return list1;
    }
    //方法二；
    public List<Character> preorderTraversal2(TreeNode root){
        List<Character> list2=new ArrayList<>();
        list2.add(root.val);
        List<Character> leftTree=preorderTraversal2(root.left);
        list2.addAll(leftTree);
        List<Character> rightTree=preorderTraversal2(root.right);
        list2.addAll(rightTree);
        return list2;
    }
    //获取二叉树中结点个数；
    public int size(TreeNode root){
        if(root==null){
            return 0;
        }
        return size(root.left)+size(root.right)+1;
    }
    //获取叶子结点个数；
    public int getLeafNodeCount(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }
    //获取二叉树的高度；
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftTree=getHeight(root.left);
        int rightTree=getHeight(root.right);
        return Math.max(leftTree,rightTree)+1;
    }
//检查value值是否存在；
    public TreeNode findVal(TreeNode root, char val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        TreeNode leftT=findVal(root.left,val);
        if(leftT!=null){
            return leftT;
        }
        TreeNode rightT=findVal(root.right,val);
        if(rightT!=null){
            return rightT;
        }
        return null;
    }
    //检查两颗数是否是相同的数；
    //方法：1、要想判断两颗数是相同的数需要结构上一样，并且value值也是一样的；
    //、、、2.如何判断结构是一样得的还是不一样的呢？需要判断是否跟的左右子数是否一样；
    //.....3如何判断value是否是一样的呢？需要判断root.val值是否相同
    //.....4.运用递归方法依次进行左子树的左右结点的比较，以及右子树得左右结点比较；
    public boolean isSameTree(TreeNode p,TreeNode q){
        //判断结构是否是一样的；
        if(p!=null&&q==null||p==null&&q!=null){
            return false;
        }
        //根据上述判断，如果代码可以能执行到这里说明两棵树的结构是一样的；
        if(q==null&&p==null){
            return true;
        }
        //根据上述代码判断，如果可以执行道这里就说明，两棵树结构上是一样的，并且左右子树也不是空的；
        //接下来，判断两棵树的根值是否是一样的？
        if(p.val!=q.val){
            return false;
        }
        //接下来，进行判断子数是否一样；
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    //判断两颗树，一棵树是否是另一颗树的子树；
    public boolean isSubtree(TreeNode root,TreeNode subroot){
        if(root==null){
            return false;
        }
        //1。判断两棵树是否是相同的树；
        if(isSameTree(root,subroot)){
            return true;
        }
        //判断该树是否是其左子树的子树；
        if(isSubtree(root.left,subroot)){
            return true;
        }
        //判断该树是否其右子树的子树；
        if(isSubtree(root.right,subroot)){
            return true;
        }
        return false;
    }
//翻转二叉树；
    //方法：将根的左右子树进行翻转；，，
    // 将根的左子树作为根将其对应的左右子树进行翻转
    // 将根的右子树作为根将其对应的左右子树进行翻转；；
    //依次类推进行递归；
    public TreeNode invertTree (TreeNode root ){
        if(root==null){
            return null;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree((root.right));
        return root;
    }
    //对称二叉树；
    //给你一个二叉树,判断这是二叉树是否是对称的；
    //方法：首先需要判断这个二叉树的左右子树是否是对称的？
    //怎么判断左右子树是对称二叉树呢？？首先需要这个左右子树结构是一致的并且值也是对称一样的。。。
    //上面对称要求的前提满足了，呢么怎么判断事对称的呢？？
    //需要判断左子树的左树是否和右树的右子树是否是对称的，以及左子树的右树是否和右子树的左树是否是对称的呢？
    public boolean isSymmetric(TreeNode root){
        if(root==null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if(leftTree!=null&&rightTree==null||leftTree==null&&rightTree!=null){
            return false;
        }
        if(leftTree==null&&rightTree==null){
            return true;
        }
        if(leftTree.val!= rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)
                &&isSymmetricChild(leftTree.right,rightTree.left);
    }
    //判断一颗树是否是平衡二叉树；
    //平衡二叉树的概念：指该树的所有结点的左右子树的深度相差不超过1；
    //如何判断呢：遍历当前树的每个节点， 求每个结点的左树和右树的高度
    // 先判断根的左右是否是平衡，再判断根左右结点作为树的时候是否平衡；
    public boolean isBalanced2(TreeNode root){
        if(root==null){
            return true;
        }
        return getHeight2(root)>=0;
    }
    public int getHeight2(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftTree=getHeight2(root.left);
        if(leftTree<0){
            return -1;
        }
        int rightTree=getHeight2(root.right);
        if(rightTree<0){
            return -1;
        }
        if(Math.abs(leftTree-rightTree)<=1){
            return Math.max(leftTree,rightTree)+1;
        }else{
            return -1;
        }

    }

//二叉搜索树与双向链表；
    //要求：输入一颗二叉搜索树，将该二叉树搜索树转换成一个排序的双向链表；
    //什么是二叉搜索树：根的左子树的值比根小，根的右子树的值比根大；
    //方法：要转换成一个有序的双向链表，所以第一要考虑到有序：
    //1.有序；采用中序遍历，可以使得得到的值有序；
    //2，考虑到双向链表要考虑前驱的后驱的顺序；所以在进行中序遍历的同时要考虑到指向问题，
    // 并且设置一个空的结点一直记录这个二叉树遍历的顺序，来完成双向链表的正确顺序与正确指向；
    TreeNode prev=null;
    public TreeNode Convert(TreeNode pRootOfTree){
        if(pRootOfTree==null){
            return null;
        }
        ConvertChild(pRootOfTree);
        TreeNode head=pRootOfTree;
        while(head.left!=null){
            head=head.left;
        }
        return head;

    }
    public void ConvertChild(TreeNode root){
        if(root==null){
            return;
        }
        ConvertChild(root.left);
        root.left=prev;
        if(prev!=null){
            prev.right=root;
        }
        prev=root;
        ConvertChild(root.right);
    }
//二叉树的遍历与构建；
    //新的构建方法，：将根据一串先序遍历得结果并且空树用#表示，来创建一个二叉树；
    //方法：1.前序遍历的顺序是：根，左。右：利用依次遍历这串字符进行遍历根左右来进行二叉树的构建；
   //,,,,,2.依次构建字符串进行结点构建遇到#就跳过不构建结点，完后依次进行左右结点的构建；
   //，，，3.最后返回构建好的二叉树的头结点；
public int i=0;
    public TreeNode createTree(String str){

        TreeNode root=null;
        if(str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
        }else{
            i++;
        }
        root.left=createTree(str);
        root.right=createTree(str);
        return root;
    }
    //层序遍历；
    //方法一：利用构建一个队列来进行完成；
    //步骤：1，设计一颗树cur来代替接收root结点；
    //.....2,将其存入队列中，完后将其出队列再次赋值给cur，并且记得打印其对应的值；
    // ，3。如果cur的左右左右子树不为空结点，就将其放入队列中，
    // 4.完后依次进行出队例判断左右结点；直到队列为空就遍历完了，说明层序遍历成功输出；
    public void levelOrder(TreeNode root){
        if(root==null){
            return;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.println(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
        System.out.println();

    }
//层序遍历 方法二;
    //要求遍历结果以二维数组的形式进行输出；
    //方法：要在方法一的基础上建立一个二维数组，来分给存放每层遍历完的字符；并且最终返回root；
    public List<List<Character>> levelOrder2(TreeNode root){
        List<List<Character>> ret=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size= queue.size();
            List<Character> list=new ArrayList<>();
            while(size!=0){
               TreeNode cur=queue.poll();
               list.add(cur.val);
               if(cur.left!=null){
                   queue.offer(cur.left);
               }
               if(cur.right!=null){
                   queue.offer(cur.right);
               }
               size--;
            }
            ret.add(list);
        }
        return ret;
    }
    //判断一棵树是不是完全二叉树；
    //判断方法有点类似上述层序遍历方法；
    //方法；建立一个队列进行接收二叉树的根结点，接着进行将放进队列的根结点取出赋值给cur，在接着利用cur来放进去其左右子树，
    //在接着,将他们一一出栈，一一赋值给cur，只有cur不为null，就一直秩序进行，
    // 直到cur为空时，就进行判断队列中除了null元素外是否还有其他元素，如果有，就说明不是完全二叉树，反之，就是二叉树；
    public boolean isCompleteTree(TreeNode root){
        if(root==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if (cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;
            }
        }
        while(!queue.isEmpty()){
            TreeNode peek=queue.peek();
            if(peek!=null){
                return false;
            }
            queue.poll();
        }
        return true;
    }
    //给定一颗二叉树，找到该数中两个指定节点的最近公共祖先；
    //方法一；
    //方法：会出现的情况：1.两个节点中有一个是根节点，呢就不用找了，其中是根节点的呢个就是公共祖先；
    // ...............2.两个结点分布在根节点的左右两侧
    //................3.两个结点都分布在根结点的左侧；
    //................4.两个结点都分布在根节点的右侧；
    //考虑问题，需要注意的是：
    // 3,4两种情况；会出现在某一侧找到一个·结点就不找了，到下一侧去寻找另一个结点去了，这样就容易出错；，应进行多方面进行考虑；
    public TreeNode lowestCommonAncestor(TreeNode root ,TreeNode p,TreeNode q){
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode leftRoot=lowestCommonAncestor(root.left,p,q);
        TreeNode rightRoot=lowestCommonAncestor(root.right,p,q);
        if(leftRoot!=null&&rightRoot!=null){
            return root;
        }else if(leftRoot!=null){
            return leftRoot;
        }else{
            return rightRoot;
        }
    }
    //给定一颗二叉树，找到该数中两个指定节点的最近公共祖先；
    //方法二：
    //思考:1.本题的目的是寻找公共祖先，呢就说明两个结点走过的路径肯定会经过一个公共结点，也就是公共祖先；
    //....2.记得在之前在链表中找公共节点的方法，这就可以利用这个方法进行寻找；
    //方法;1，建立两个栈，其中一个放一个结点走过的路径，另一个栈放另一个结点走过的路径；
    //    2.比较两个栈中元素的多少，多的出两个对应的差值；
    //    3.直到两个栈中元素相同就一起出元素，别出别判断元素是否相同，相同就说明是两个结点的公共祖先；
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack ){
        if(root==null){
            return false;
        }
        stack.push(root);
        if(root==node){
            return true;
        }
        boolean ret=getPath(root.left,node,stack);
        if(ret){
            return true;
        }
        ret=getPath(root.left,node,stack);
        if(ret){
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root,TreeNode p,TreeNode q){
        if(root==null){
            return null;
        }
        //1.建立两个栈来保存两个结点走过的路径；
        Stack<TreeNode> stackP=new Stack<>();
        Stack<TreeNode> stackQ=new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);
        //2.计算两个栈的大小，大的出两个对应的差值；
        int sizeP= stackP.size();
        int sizeQ= stackQ.size();
        if(sizeP>sizeQ){
            int size=sizeP-sizeQ;
            while(size!=0){
                stackP.pop();
                size--;
            }
        }else{
            int size=sizeQ-sizeP;
            while(size!=0){
                stackQ.pop();
                size--;
            }
        }
        //3.进行两栈同时出元素，看两个元素是否相同，
        while(!stackP.isEmpty()&&!stackQ.isEmpty()){
            if(stackP.peek()==stackQ.peek()){
                return stackP.peek();
            }else{
                stackP.pop();
                stackQ.pop();
            }
        }
        return null;
    }
//根据二叉树创建字符串；
    //要求：给定一格二叉树根结点root，采用前序遍历得方式，将二叉树转换为一个由括号和整数组成的字符串，并且返回构造出的字符串；
    //....空节点采用一对括号表示，
    //方法：。先拼接根结点的值，再进行判断根的左节点是否为空，若不为空，就拼接一个左括号，直到遇见空结点就返回，返回后要判断拼接一个右括号。
    ////////接着进行判断右节点，同样的方法依次递归；
    //注意：1.若一个子根结点的左右结点都为空就直接返回，拼接一个右括号即可，作为结束标志；
    //......2.若一个子根左节点为空，右节点不为空，在结束判完左节点后就拼接一个完整的双括号；
    public String tree2str(TreeNode root){
        if(root==null){
            return null;
        }
        //实例化一个拼接类；
        StringBuilder stringBuilder=new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void tree2strChild(TreeNode t,StringBuilder stringBuilder){
        if(t==null){
            return ;
        }
        stringBuilder.append(t.val);
        if(t.left!=null){
            stringBuilder.append("(");
            tree2strChild(t.left,stringBuilder);
            stringBuilder.append(")");
        }else{
            if(t.right==null){
                return;
            }else{
                stringBuilder.append("()");
            }
        }
        if(t.right!=null){
            stringBuilder.append("(");
            tree2strChild(t.right,stringBuilder);
            stringBuilder.append(")");
        }else{
            return;
        }
    }

    //二叉树非递归实现前序遍历；
    //思路：1，先构建一个栈来进行存放，遍历二叉树的根和左右结点；
    //.....2。设计一棵树cur来代替接收根节点；利用cur进行依次出栈，遍历二叉树的左结点，只有cur不为空，就一直遍历二叉树左分支；
    //    3.当cur为空后，说明左节点遍历完成，这是建立一个新的树来接收从栈中取出的父亲节点，并且将其右节点赋值给cur。使得cur重新进行上述方法；
    //这样利用栈就完成了，最底层子根和左右结点的遍历，依次找父亲根进行遍历，最总完成所有结点的遍历；
    public void preOrderNor(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                System.out.println(cur.val+"");
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }
    }
    //二叉树用非递归方法进行实现后序遍历；
    //思路：建立一个栈进行存放二叉树的节点，
    // 之后进行向栈中一一放对应的元素，完后进行一一出栈赋值给cur，若cur不为空就继续放入栈中左分支节点，若为空，就退出循环
    // 当退出循环后就要定义一颗新的树进行查看栈中元素，将栈中元素取出，并将其右节点赋值给cur，来遍历右分支；；
    // 但是防止回退出现死循环，要将已经判断完的结点进行记录防止在被cur进行遍历，
    public void postOrderNor(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prep=null;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur.left);
                cur=cur.left;
            }
            TreeNode top=stack.peek();
            if (top.right!=null||top.right==prep){
                System.out.println(top.val+" ");
                stack.pop();
                prep=top;
            }else{
                cur=top.right;
            }

        }
    }
}
